package com.code.leetcode.center50;

import com.code.leetcode.utils.TreeNode;
import com.sun.corba.se.spi.orbutil.fsm.FSM;
import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/26 10:03
 */
public class The106 {

    int[] inorder, postorder;
    Map<Integer, Integer> map = new HashMap<>();
    int post_idx;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        post_idx = postorder.length - 1;
        int idx = 0;
        for (int i : inorder) {
            map.put(i, idx++);
        }
        return dfs(0, post_idx);
    }

    public TreeNode dfs(int in_left, int in_right) {
        if (in_left > in_right) return null;
        int root = postorder[post_idx];
        int index = map.get(root);
        TreeNode node = new TreeNode(root);
        post_idx--;
        node.right = dfs(index + 1, in_right);
        node.left = dfs(in_left, index - 1);
        return node;
    }

}
